package com.qimingyu.linkedlist.singlylinkedlist;

/**
 * 带哨兵的单链表
 */
public class SinglyLinkedListWithGuard {
    private Node head = new Node(666, null);//头指针指向一个value为666的哨兵节点

    private static class Node {//用内部类的形式
        int value;//结点的值
        Node next;//next指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    //实现头插法（哨兵版本）
    public void addFirst(int value) {
        head.next = new Node(value, head.next);
    }

    //链表的循环遍历(哨兵版本)
    public void loopPrint() {
        //创建一个指针指向头结点指向的结点，即为链表中的第一个结点
        Node p = head.next;
        while (p != null) {
            System.out.print(p.value + "  ");
            p = p.next;
        }
        System.out.println();
    }

    /**
     * 尾插法（ 哨兵版本）
     *
     * @param value
     */
    public void addTail(int value) {
        //如果链表只有一个哨兵，直接插入到哨兵结点的后面(等同于头插法)
        if (head == null) {
            head.next = new Node(value, head.next);
            return;
        }

        //如果链表不为空插入到当前链表的末尾
        Node p = head.next;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value, null);
    }

    //清空链表
    public void cleanList() {
        head.next = null;
    }

    /**
     * 在指定的位置插入节点（带哨兵版本）
     * <p>
     * 例如在index为2的位置插入一个value为10的值
     *
     * @param index
     * @param value
     */
    public void insert(int index, int value) {
        Node p = head.next;
        int position = 0;
        //遍历链表找到插入位置
        while (position < index) {
            p = p.next;
            position++;
        }
        //遍历链表找到要插入位置的上一个结点
        Node pre = head;
        while (pre.next != p) {
            pre = pre.next;
        }
        //新节点指向要插入位置的原结点，
        //插入位置的上一个结点指向新结点
        pre.next = new Node(value, p);
    }

    /**
     * 删除指定位置的结点
     *
     * @param index
     */
    public void delete(int index) {
        //遍历找到要删除位置的结点
        Node p = head.next;
        int position = 0;
        while (position < index) {
            p = p.next;
            position++;
        }
        //遍历找到要删除位置结点的上一个结点
        Node pre = head;
        while (pre.next != p) {
            pre = pre.next;
        }
         //把上一个位置的结点的指针指向原位置的下一个结点
        pre.next = p.next;
    }

    public static void main(String[] args) {
        SinglyLinkedListWithGuard listWithGuard = new SinglyLinkedListWithGuard();
        System.out.print("头插法插入几个数据后的链表为：  ");
        listWithGuard.addFirst(0);
        listWithGuard.addFirst(1);
        listWithGuard.addFirst(2);
        listWithGuard.addFirst(3);
        listWithGuard.loopPrint();
        System.out.print("尾插法插入一个4后的链表为：  ");
        listWithGuard.addTail(4);
        listWithGuard.loopPrint();

        listWithGuard.insert(2,10);
        System.out.print("在index为2的地方插入一个值为10的结点：    ");
        listWithGuard.loopPrint();
        System.out.print("在index为3的地方删除一个结点：    ");
        listWithGuard.delete(3);
        listWithGuard.loopPrint();
    }
}